import java.util.*;

public class Solution {
    public static void main(String[] args) {

    }

    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        /**
         * 找出知晓秘密的所有专家Ⅱ
         * 解题逻辑：
         *  1，按照时间对会议进行排序
         *  2，对同一时间段与会人员进行合并，若是同一集合中存在一个人知情，则整体知情（连通关系）
         *  3，处理完所有会议后统计知情人数*/
        // 1 预处理
        Arrays.sort(meetings, (a,b) -> a[2]-b[2]);
        initialize(n);
        aware[0] = aware[firstPerson] = true;
        // -记录时间
        int curTime = 0;
        // -暂存每一阶段与会人员
        int[] tempStorage = new int[20_0000];
        int tempIndex = 0;

        // 2 处理会议数据
        for(int[] e: meetings) {
            // -2.1 判断时间段（相异则更新并释放上一时间段不知情人员）
            if(curTime != e[2]) {
                while(tempIndex > 0) {
                    int curValue = tempStorage[--tempIndex];
                    if(!aware[find(curValue)]) {
                        father[curValue] = curValue;
                    }
                }
                curTime = e[2];
            }
            // -2.2 合并与会人员
            union(e[0], e[1]);
            tempStorage[tempIndex++] = e[0];
            tempStorage[tempIndex++] = e[1];
        }

        // 3 统计知情人数
        List<Integer> answer = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            if(aware[find(i)]) {
                answer.add(i);
            }
        }
        return answer;
    }

    // 创建简易并查集
    public static int MAX_N;
    public static int[] father;
    public static int[] size;
    public static int[] stack;
    // -添加知情标签
    public static boolean[] aware;

    public static void initialize(int n) {
        /**
         * 初始化并查集*/
        MAX_N = n;
        father = new int[MAX_N];
        size = new int[MAX_N];
        stack = new int[MAX_N];
        aware = new boolean[MAX_N];
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到a所在集合的代表元素+扁平化*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否属于同一集合*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合+小挂大*/
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                aware[fa] = aware[fa] || aware[fb];
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                aware[fb] = aware[fa] || aware[fb];
                father[fa] = fb;
            }
        }
    }
}
